
class Solution:
    def strStr(self, source, target):
        digit = 7
        mod   = 3079
        len_s = len(source)
        len_p = len(target)

        if len_p > len_s :
            return -1

        digit_expo = (digit ** len_p) % mod

        s_hash = 0
        p_hash = 0
        for i in range(len_p):
            # print('here')
            s_hash = (s_hash * digit + ord(source[i])) % mod
            p_hash = (p_hash * digit + ord(target[i])) % mod

        # print(s_hash, p_hash)

        for i in range(0, len_s - len_p+1):
            if s_hash == p_hash:
                # print('here')
                if source[i:i+len_p] == target:
                    return i
            else:
                if i + len_p < len_s:
                    s_hash = (s_hash * digit + ord(source[i+len_p]) - ord(source[i]) * digit_expo) % mod

        return -1
